package com.github.hgkmail.hello.leetcode101.pointer.linkedlist;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.ListNode;

/**
 * 两种思维
 * 1.从尾部串起来（数组思维）：这道题很难
 * 2.改变链表指针的方向（链表思维）：这道题简单
 */
public class LC92ReverseLinkedList2 {

    //虽然知道这道题是改变链表指针的方向，但还是要[画图]来辅助写代码，不然容易被next指针搞晕。。。
    //思路通常都不难，写对链表问题的技巧是：一定要先想清楚思路，并且必要的时候在草稿纸上[画图]，理清「穿针引线」的先后步骤，然后再编码。
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //不用反转的情况
        if (head==null || head.next==null || left==right) {
            return head;
        }
        ListNode prev=null;
        ListNode curr=head;
        ListNode temp;
        int i=1;
        while (i<left) {
            temp=curr.next;
            prev=curr;
            curr=temp;
            i++;
        }
        //把[开始处]的节点记录下来，后面有用
        ListNode begin1=prev;
        ListNode begin2=curr;

        //当成简单的整体反转链表
        prev=null;
        while (i<=right) {
            temp=curr.next;
            curr.next=prev;
            prev=curr;
            curr=temp;
            i++;
        }
        //把[结束处]的节点记录下来，后面有用
        ListNode end1=prev;
        ListNode end2=curr;

        //缝合链表
        if (begin1!=null) {
            begin1.next=end1;
        }
        if (begin2!=null) {
            begin2.next=end2;
        }

        if (begin1!=null) {
            return head;
        } else {
            return end1;
        }
    }

    public static void main(String[] args) {
        ListNode a, b, c, d, e;
//        e=new ListNode(5, null);
//        d=new ListNode(4, e);
        c=new ListNode(3, null);
        b=new ListNode(2, c);
        a=new ListNode(1, b);
        CommonUtil.printLinkedList(a);

        CommonUtil.printLinkedList(new LC92ReverseLinkedList2().reverseBetween(a, 1,2));
    }
}
